package com.wkh.datastructure;

import java.util.Iterator;

/**
 * 带哨兵的双向链表
 */
public class DoublyLinkedSentinelList<E> implements Iterable<Object>{

    private Node head;
    private Node tail;

    public DoublyLinkedSentinelList() {
        head = new Node(null,999,null);
        tail = new Node(null,999,null);
        head.next = tail;
        tail.prev = head;
    }
    //头插
    public void addFirst(Object value){
        insert(value,0);
    }
    public void insert(Object value,int index){
        Node prev = findNode(index - 1);//插入结点的前一个结点
        if (prev == null){//判断索引是否合法
            illegalIndex(index);
            return;
        }
        Node next = prev.next;//插入结点的后一个结点
        Node inserted = new Node(prev, value, next);
        prev.next = inserted;
        next.prev = inserted;

    }

    public void removeFirst(){
        remove(0);
    }

    public void remove(int index){
        Node prev = findNode(index-1);
        if (prev == null){
            illegalIndex(index);
        }
        Node removed = prev.next;
        if (removed == tail){
            illegalIndex(index);
        }
        Node next = removed.next;
        prev.next = next;
        next.prev = prev;
    }

    //尾插
    public void addLast(Object value){
        Node prev = tail.prev;
        Node node = new Node(prev, value, tail);
        prev.next = node;
        tail.prev = node;
    }
    //尾删
    public void removeLast(){
        Node removed = tail.prev;
        if (removed == head){
            illegalIndex(0);
        }
        Node prev = removed.prev;
        prev.next = tail;
        tail.prev = prev;
    }
    private void illegalIndex(int index) {
        throw new IllegalArgumentException("index:"+ index+ "不合法");
    }

    //找到对应索引的结点
    private Node findNode(int index){
        int i = -1;//表示头哨兵的结点
        for (Node p = head;p != tail;p = p.next,i++){
            if (i == index){
                return p;
            }
        }
        return null;
    }

    /**
     * Returns an iterator over elements of type {@code T}.
     *
     * @return an Iterator.
     */
    @Override
    public Iterator<Object> iterator() {

        return new Iterator<Object>() {
            Node node = head.next;
            @Override
            public boolean hasNext() {
                return node != tail;
            }

            @Override
            /**
             * 返回结点的值并指向下一个结点
             */
            public Object next() {
                Object value = node.value;
                node = node.next;
                return value;
            }
        };
    }

    private static class Node{
        private Node prev;
        private Object value;
        private Node next;

        public Node(Node prev, Object value, Node next) {
            this.prev = prev;
            this.value = value;
            this.next = next;
        }
    }
}

